package 面试真题;

import java.util.Scanner;

/**
 * @author 帅小伙
 * @date 2022/1/22
 * @description
 * 删除几个字符得到的回文子序列的最长
 */
public class Demo01腾讯2017暑假实习生编程题 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            System.out.println(solution(sc.nextLine()));
        }

    }

    public  static int solution(String str){
        int n =  str.length();
        int[][] dp = new int[n][n];
        int ans = Integer.MAX_VALUE;
        for (int i = n-1; i >= 0 ; i--) {
            dp[i][i] = 1;
            char c1 = str.charAt(i);
            for (int j = i+1; j < n; j++) {
                char c2 = str.charAt(j);
                if(c1 == c2){
                   dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                }

            }

        }
        return n - dp[0][n-1];
    }
}
